package h0829;

import java.util.HashMap;

public class LRUCache2 {
    static class DlinkedNode{
        int key;
        int val;
        DlinkedNode prev;
        DlinkedNode next;

        public DlinkedNode() {
        }

        public DlinkedNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private HashMap<Integer,DlinkedNode> cache=new HashMap<>();
    int capacity;
    int size;
    DlinkedNode head,tail;

    public LRUCache2(int capacity) {
        this.size=0;
        this.capacity = capacity;
        head=new DlinkedNode();
        tail=new DlinkedNode();
        head.next=tail;
        tail.prev=head;
    }

    public int get(int key){
        DlinkedNode node = cache.get(key);
        if (node==null){
            return -1;
        }
        //移动到头部
        moveToHead(node);
        return node.val;
    }

    public void put(int key,int value){
        DlinkedNode node = cache.get(key);
        if (node==null){
            DlinkedNode newNode = new DlinkedNode(key, value);
            //添加进哈希表
            cache.put(key,newNode);
            addToHead(newNode);
            size++;
            if (size>capacity){
                Integer k=removeTail();
                cache.remove(k);
                size--;
            }
        }else {
            node.val=value;
            //移动到队头
            moveToHead(node);
        }
    }

    private Integer removeTail() {
        DlinkedNode node = tail.prev;
        //这里删除的其实是尾节点的前一个节点
        node.prev.next=node.next;
        node.next.prev=node.prev;
        return node.key;
    }

    //添加到头部
    private void addToHead(DlinkedNode newNode) {
       newNode.prev=head;
       newNode.next=head.next;
       head.next.prev=newNode;
       head.next=newNode;
    }

    //移动到头部
    private void moveToHead(DlinkedNode node) {
        //node的前驱和后继
        node.prev.next=node.next;
        node.next.prev=node.prev;

        node.prev=this.head;
        node.next=this.head.next;
        this.head.next.prev=node;
        this.head.next=node;
    }

    public static void main(String[] args) {
        LRUCache2 cache = new LRUCache2(2);
        cache.put(1,1);
        cache.put(2,2);
        System.out.println(cache.get(1));
        cache.put(3,3);
        System.out.println(cache.get(2));
    }
}
